package leetcode100;

import java.util.*;

public class lc028 {

    public static void main(String[] args) {
        int[] nums = new int[]{-1,0,1,2,-1,-4,-2,-3,3,0,4};
        System.out.println(new lc028().threeSum(nums));
    }

    public List<List<Integer>> threeSum(int[] nums) {
//        System.out.println("nums = " + Arrays.toString(nums));



        int n = nums.length;
        int[] sums = new int[n];
        for (int i = 0; i < n; i++) {
            sums[i] = -nums[i];
        }
//        System.out.println("sums = " + Arrays.toString(sums));

        /**
         * Map < 需要的数 , 当前数索引 >
         *
         */
        List<List<Integer>> res = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        Set<String> set = new HashSet<>();


        int[] copyNums = Arrays.copyOf(nums,n);
        Arrays.sort(copyNums);
        if (copyNums[0]==0 && copyNums[nums.length-1]==0) {
            List<Integer> list  =Arrays.asList(0,0,0);
            res.add(list);
            return res;
        }
        for (int i = 0; i < n; i++) {
//            System.out.println("set: " + set);
            for (int j = i+1; j < n; j++) {
                if (map.containsKey(nums[j])) {
                    if (i != j
                            && i != map.get(nums[j])
                            && j != map.get(nums[j])) {
                        int a = nums[i];
                        int b = nums[j];
                        int c= nums[map.get(nums[j])];

                        int[] temp = {a,b,c};
                        Arrays.sort(temp);
                        String s =  temp[0]+","+temp[1]+","+temp[2];
                        if (set.add(s)) {
                            res.add(Arrays.asList(temp[0],temp[1],temp[2]));
                        }

                        continue;
                    }
                }
                map.put(sums[i] - nums[j], j);
            }
            map.clear();
        }
        return res;
    }
}
